﻿// 0819train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

/*
 定义构造三叉搜索树规则如下：
每个节点都存有一个数，当插入一个新的数时，从根节点向下寻找，直到找到一个合适的空节点插入。
查找的规则是： 
1. 如果数小于节点的数减去 500，则将数插入节点的左子树 
2. 如果数大于节点的数加上 500，则将数插入节点的右子树 
3. 否则，将数插入节点的中子树
给你一系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度。
输入描述
第一行为一个数 N，表示有 N 个数，1 <= N <= 10000
第二行为 N 个空格分隔的整数，每个数的范围为[1, 10000]

输出描述
输出树的高度(根节点的高度为 1)

输入
5
5000 2000 5000 8000 1800
输出
3
 */

class Solution01
{
public:
    struct TreeNode
    {
        int val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode* middle = nullptr;

        TreeNode() = default;
        TreeNode(int val): val(val) {};
    };
    vector<vector<int>>result;
    void reviewTreeNode(TreeNode* root)
    {
        queue<TreeNode*>bfs_queue;
        bfs_queue.push(root);

        int level = 0;
        while (!bfs_queue.empty())
        {
            level++;
            int q_size = bfs_queue.size();
            //vector<int>curr_vec;
            for (int i=0; i<q_size; i++)
            {
                TreeNode* top_node = bfs_queue.front();
                bfs_queue.pop();
                //curr_vec.push_back(top_node->val);

                if (top_node->left!=nullptr)
                {
                    bfs_queue.push(top_node->left);
                }
                if (top_node->right!=nullptr)
                {
                    bfs_queue.push(top_node->right);
                }
                if (top_node->middle!=nullptr)
                {
                    bfs_queue.push(top_node->middle);
                }

            }
            //result.push_back(curr_vec);
        }

        //for (auto&min_vec:result)
        //{
        //    for (auto&num:min_vec)
        //    {
        //        cout << num << ' ';
        //    }
        //    cout << '\n';
        //}

        cout << level;
    }

    void insertNode(TreeNode*root, int val)
    {
        if (root == nullptr) return;

        while (root)
        {
            if (val < (root->val - 500))
            {
                if (root->left==nullptr)
                {
                    root->left = new TreeNode(val);
                    break;
                }
                root = root->left;
            }
            else if (val>(root->val + 500))
            {
                if (root->right==nullptr)
                {
                    root->right = new TreeNode(val);
                    break;
                }
                root = root->right;
            }
            else
            {
                if (root->middle==nullptr)
                {
                    root->middle = new TreeNode(val);
                    break;
                }
                root = root->middle;
            }

        }
	    
    }

    void solve01(vector<int>&tree_vec)
    {
        TreeNode* root = new TreeNode(tree_vec[0]);
        for (int i=1; i<tree_vec.size();i++)
        {
            insertNode(root, tree_vec[i]);
        }
        reviewTreeNode(root);
    }
};

struct TreeNode
{
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode() = default;
    TreeNode(int val) :val(val) {};
};

TreeNode* BuildNode(vector<int>&tree_vec)
{
    TreeNode* root = new TreeNode(tree_vec[0]);

    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    int index = 1;
    while (!bfs_queue.empty() && index<tree_vec.size())
    {
        TreeNode* top_node = bfs_queue.front();
        bfs_queue.pop();

        if (top_node->left==nullptr && tree_vec[index]!=INT_MIN)
        {
            top_node->left = new TreeNode(tree_vec[index]);
            bfs_queue.push(top_node->left);
        }
        index++;
        if (top_node->right==nullptr&& tree_vec[index]!=INT_MIN)
        {
            top_node->right = new TreeNode(tree_vec[index]);
            bfs_queue.push(top_node->right);
	        
        }
        index++;
    }
    return root;
}

class Solution02
{
public:
    void insertNode(TreeNode* root, int val)
    {
        while (root)
        {
            if (val < root->val)
            {
                if (root->left == nullptr)
                {
                    root->left = new TreeNode(val);
                    break;
                }
                root = root->left;

            }
            else if (val > root->val)
            {
                if (root->right == nullptr)
                {
                    root->right = new TreeNode(val);
                    break;
                }
                root = root->right;
            }

        }
    }

    TreeNode* insertIntoBST(TreeNode* root, int val)
    {
        if (root == nullptr)
            return new TreeNode(val);
        insertNode(root, val);
        return root;
    }
};



int main()
{
	{
        //root = [4,2,7,1,3], val = 5
        vector<int>tree_vec = { 4,2,7,1,3 };
        int val = 5;
        TreeNode* root = BuildNode(tree_vec);

        Solution02 solu;
        solu.insertIntoBST(root, val);

        return 0;
	}
    //5
	//5000 2000 5000 8000 1800
    vector<int>tree_vec = { 5000,2000,5000,8000,1800 };
    //int vec_size;
    //cin >> vec_size;
    //vector<int>tree_vec(vec_size);
    //for (int i=0; i<vec_size; i++)
    //{
    //    cin >> tree_vec[i];
    //}
    
    Solution01 solu;
    solu.solve01(tree_vec);
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
